---
title: C 算法设计
---

## 考点
算法设计是下午软件设计中最难的题型，<RedSpan>主要难在 C 代码填空上</RedSpan>。
1. 代码填空：第一小题，最后解决。
2. 算法、时间复杂度：第二题，先做，考察何种算法很好分辨，涉及到分组就是分治法，局部最优就是贪心法，整体规划最优就是动态规划法，迷宫类的问题就是回溯法，记住关键字很好区分；时间复杂度就是看 C 代码中的 for 循环层数和每一层的循环次数，涉及到二分必然有 $O(log_n)$。
3. 特殊值计算：第三小题，一般应该先做，不需要根据 C 代码，<RedSpan>直接根据题目给出的算法原理，一步步推导即可得出答案</RedSpan>

## 算法类型判断
算法基本上只考四种，分治算法、动态规划算法、贪心法、回溯法，在题目中找关键字。

* 出现最优、最大、最小： 从动态规划法和贪心法中寻找，贪心法是局部最优；动态规划法是全局最优，要求每一步子结构都是最优的，动态规划法会使用递归的思想去求，一般会给出最优子结构的递归式。
* 有分而治之的思想，就是分治法
* 回溯法： 回溯
### 算法一
<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241016234811.png"/>

动态规划法：最优子结构、递归、公式

### 算法二
<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241016234902.png"/>

### 算法三
<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241016235124.png"/>

出现最优，选动态规划法和贪心法，出现递归公式，则为动态规划法。


### 算法四
<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241016235341.png"/>


出现最优，选动态规划法和贪心法，出现递归公式，则为动态规划法。
### 算法五
<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241016235438.png"/>

<RedSpan>分而治之的思想，分治法</RedSpan> ，不是二分查找法

### 算法六
<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241016235718.png"/>


贪心法：求最优，但没有最优子结构、递归等。